class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

export class LinkList<T> {
  //protected修饰符是ts语法
  //保护类的方法能被继承并且在类里访问，但是外界访问不到

  //头指针
  protected head: Node<T> | null = null;
  //尾指针
  protected tail: Node<T> | null = null;
  //长度
  protected size: number = 0;
  //获取长度
  get length() {
    return this.size;
  }
  //是否是尾部节点
  private isTail(node: Node<T>): boolean {
    // return node.next===null||node.next===this.head
    return this.tail === node;
  }

  //给出位置返回当前节点
  getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current.next;
    }

    return current;
  }

  //追加节点
  append(value: T) {
    //根据value创建第一个节点
    const newNode = new Node(value);

    //判断this.head是否为null
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
    }
    this.tail = newNode;
    this.size++;
  }

  //遍历链表的方法（循环链表重构）
  traverse() {
    const arr: T[] = [];
    let current = this.head;
    while (current) {
      arr.push(current.value);
      if (this.isTail(current)) {
        //是最后一个节点
        current = null;
      } else {
        //不是最后一个节点
        current = current.next;
      }
    }

    if (this.head && this.tail?.next === this.head) {
      arr.push(this.head.value);
    }

    console.log(arr.join(" --> "));
    return arr;
  }

  //插入数据
  insert(value: T, position: number): boolean {
    if (position < 0 || position > this.size) {
      throw new Error("插入的位置已越界");
    }
    const newNode = new Node(value);
    if (position === 0) {
      //头部插入
      newNode.next = this.head;
      this.head = newNode;
    } else {
      //双指针插入
      let previous = this.getNode(position - 1);
      newNode.next = previous!.next;
      previous!.next = newNode;
      if (position === this.size) {
        this.tail = newNode;
      }
    }
    this.size++;
    return true;
  }

  //移除数据
  removeAt(position: number): T | null {
    if (position < 0 || position > this.size) {
      throw new Error("移除的位置已越界");
    }

    let current = this.head;
    if (position === 0) {
      this.head = current?.next ?? null;
      if (this.size === 1) {
        this.tail = null;
      }
    } else {
      let previous = this.getNode(position - 1);
      current = previous?.next ?? null;
      previous!.next = current?.next ?? null;

      //索引从0开始
      if (position === this.size - 1) {
        this.tail = previous;
      }
    }

    this.size--;
    return current?.value || null;
  }

  //获得当前位置的元素
  get(position: number): T | null {
    if (position < 0 || position > this.size) {
      throw new Error("查找元素位置已越界，不在链表中");
    }
    let current = this.getNode(position - 1);

    return current?.value || null;
  }

  //修改
  update(value: T, position: number): boolean {
    if (position < 0 || position > this.size) {
      throw new Error("查找元素位置已越界，不在链表中");
    }
    let current = this.getNode(position);
    current!.value = value;
    return true;
  }

  //根据元素查找下标
  indexOf(value: T): number {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.value === value) {
        return index;
      }
      if (this.isTail(current)) {
        current = current.next;
      } else {
        current = null;
      }
      index++;
    }
    return -1;
  }

  //根据传入的元素删除
  remove(value: T): T | null {
    const index = this.indexOf(value);
    return this.removeAt(index);
  }

  //是否是空
  isEmpty(): boolean {
    return this.size === 0;
  }
}

// const linkedList = new LinkList<string>();

// linkedList.append(`aaa`);
// linkedList.append(`bbb`);
// linkedList.append(`ccc`);
// linkedList.insert("abc", 0);
// linkedList.traverse();
// linkedList.insert("def", 3);
// linkedList.traverse();
// // console.log(linkedList.removeAt(1), "remove---");
// // linkedList.traverse();
// // console.log(linkedList.removeAt(2));
// // linkedList.traverse();
// // console.log(linkedList.get(-1));
// // console.log(linkedList.get(3));

// console.log(`-----更新-----`);
// console.log(linkedList.update(`111`, 0));
// linkedList.traverse();
// console.log(linkedList.indexOf(`cccd`));
